home *** CD-ROM | disk | FTP | other *** search
/ Personal Computer World 2005 October / PCWOCT05.iso / Software / FromTheMag / XAMPP 1.4.14 / xampp-win32-1.4.14-installer.exe / xampp / php / pear / Math / Fibonacci.php < prev    next >
PHP Script  |  2004-03-24  |  17KB  |  490 lines
  1. <?php
  2. //
  3. // +----------------------------------------------------------------------+
  4. // | PHP Version 4                                                        |
  5. // +----------------------------------------------------------------------+
  6. // | Copyright (c) 1997-2002 The PHP Group                                |
  7. // +----------------------------------------------------------------------+
  8. // | This source file is subject to version 2.0 of the PHP license,       |
  9. // | that is bundled with this package in the file LICENSE, and is        |
  10. // | available at through the world-wide-web at                           |
  11. // | http://www.php.net/license/2_02.txt.                                 |
  12. // | If you did not receive a copy of the PHP license and are unable to   |
  13. // | obtain it through the world-wide-web, please send a note to          |
  14. // | license@php.net so we can mail you a copy immediately.               |
  15. // +----------------------------------------------------------------------+
  16. // | Authors: Jesus M. Castagnetto <jmcastagnetto@php.net>                |
  17. // +----------------------------------------------------------------------+
  18. //
  19. // $Id: Fibonacci.php,v 1.1 2003/01/02 01:56:59 jmcastagnetto Exp $
  20. //
  21.  
  22. include_once 'PEAR.php';
  23. include_once 'Math/IntegerOp.php';
  24. include_once 'Math/Fibonacci/_fibonacciTable.php';
  25.  
  26. // PHI and phi are the roots of: x^2 - x - 1 = 0
  27. // PHI is called the golden ratio. Also phi = -1/PHI = 1 - PHI
  28. /**
  29.  * MATH_PHI: The golden ratio = (1 + sqrt(5))/2
  30.  */
  31. define ('MATH_PHI', (1 + sqrt(5))/2);
  32. /**
  33.  * MATH_PHI_x100000: (int) (MATH_PHI * 100000)
  34.  */
  35. define ('MATH_PHI_x100000', intval(MATH_PHI * 100000));
  36.  
  37. /**
  38.  * MATH_phi: The reciprocal of PHI = (1 - sqrt(5))/2
  39.  */
  40. define ('MATH_phi', (1 - sqrt(5))/2);
  41. /**
  42.  * MATH_phi_x100000: (int) (MATH_phi * 100000)
  43.  */
  44. define ('MATH_phi_x100000', intval(MATH_phi * 100000));
  45.  
  46. /**
  47.  * MATH_SQRT5_x100000: (int) (sqrt(5) * 100000)
  48.  */
  49. define ('MATH_SQRT5_x100000', intval(sqrt(5) * 100000));
  50.  
  51. /**
  52.  * MATH_LNSQRT5: ln(sqrt(5))
  53.  */
  54. define ('MATH_LNSQRT5', log(sqrt(5)));
  55.  
  56. /**
  57.  * MATH_LNPHI: ln(PHI)
  58.  */
  59. define ('MATH_LNPHI', log(MATH_PHI));
  60.  
  61. /**
  62.  * Math_Fibonacci: class to calculate, validate, and decompose into Fibonacci numbers
  63.  *
  64.  * Examples:
  65.  * <pre>
  66.  * include_once 'Math/Fibonacci.php';
  67.  * 
  68.  * $idx = 20;
  69.  * echo "Calculate F($idx), fast equation = ";
  70.  * $fib =& Math_Fibonacci::term($idx);
  71.  * echo $fib->toString()."\n";
  72.  * // Calculate F(20), fast equation = 6765
  73.  * 
  74.  * $idx = 55;
  75.  * echo "Calculate F($idx), lookup table = ";
  76.  * $fib =& Math_Fibonacci::term($idx);
  77.  * echo $fib->toString()."\n";
  78.  * // Calculate F(55), lookup table = 139583862445
  79.  * 
  80.  * $idx = 502;
  81.  * echo "Calculate F($idx), addition loop = ";
  82.  * $fib = Math_Fibonacci::term($idx);
  83.  * echo $fib->toString()."\n";
  84.  * // Calculate F(502), addition loop = 365014740723634211012237077906479355996081581501455497852747829366800199361550174096573645929019489792751
  85.  * 
  86.  * echo "\nSeries from F(0) to F(10):\n";
  87.  * $series = Math_Fibonacci::series(10);
  88.  * foreach ($series as $n=>$fib) {
  89.  *     echo "n = $n, F(n) = ".$fib->toString()."\n";
  90.  * }
  91.  * // Series from F(0) to F(10):
  92.  * // n = 0, F(n) = 0
  93.  * // n = 1, F(n) = 1
  94.  * // n = 2, F(n) = 1
  95.  * // n = 3, F(n) = 2
  96.  * // n = 4, F(n) = 3
  97.  * // n = 5, F(n) = 5
  98.  * // n = 6, F(n) = 8
  99.  * // n = 7, F(n) = 13
  100.  * // n = 8, F(n) = 21
  101.  * // n = 9, F(n) = 34
  102.  * // n = 10, F(n) = 55
  103.  * 
  104.  * echo "\nand now from F(11) to F(19):\n";
  105.  * $series = Math_Fibonacci::series(11, 19);
  106.  * foreach ($series as $n=>$fib) {
  107.  *     echo "n = $n, F(n) = ".$fib->toString()."\n";
  108.  * }
  109.  * // and now from F(11) to F(19):
  110.  * // n = 11, F(n) = 89
  111.  * // n = 12, F(n) = 144
  112.  * // n = 13, F(n) = 233
  113.  * // n = 14, F(n) = 377
  114.  * // n = 15, F(n) = 610
  115.  * // n = 16, F(n) = 987
  116.  * // n = 17, F(n) = 1597
  117.  * // n = 18, F(n) = 2584
  118.  * // n = 19, F(n) = 4181
  119.  *
  120.  * echo "\nChecking if 26 and 4181 are Fibonacci numbers\n";
  121.  * $verb = Math_Fibonacci::isFibonacci(new Math_Integer(26)) ? 'is' : 'is not';
  122.  * echo "26 $verb a Fibonacci number\n";
  123.  * // 26 is not a Fibonacci number
  124.  * $verb = Math_Fibonacci::isFibonacci(new Math_Integer(4181)) ? 'is' : 'is not';
  125.  * echo "4181 $verb a Fibonacci number\n";
  126.  * // 4181 is a Fibonacci number
  127.  * 
  128.  * echo "\nDecompose 34512\n";
  129.  * $decarr = Math_Fibonacci::decompose(new Math_Integer(34512));
  130.  * foreach ($decarr as $fib) {
  131.  *     $index = Math_Fibonacci::getIndexOf($fib);
  132.  *     echo "F(".$index->toString().") = ".$fib->toString()."\n";
  133.  * }
  134.  * // Decompose 34512
  135.  * // F(23) = 28657
  136.  * // F(19) = 4181
  137.  * // F(17) = 1597
  138.  * // F(10) = 55
  139.  * // F(8) = 21
  140.  * // F(2) = 1
  141.  * 
  142.  * echo "\nF(n) closest to 314156 is: ";
  143.  * $fib = Math_Fibonacci::closestTo(new Math_Integer(314156));
  144.  * echo $fib->toString()."\n\n";
  145.  * // F(n) closest to 314156 is: 317811
  146.  * 
  147.  * echo 'The index for 1597 is : ';
  148.  * $idx = Math_Fibonacci::getIndexOf(new Math_Integer(1597));
  149.  * echo $idx->toString()."\n\n";
  150.  * // The index for 1597 is : 17
  151.  * 
  152.  * $bigint = '3141579834521345220291';
  153.  * echo "Finding the Fibonacci numbers that add up to $bigint\n";
  154.  * $series = Math_Fibonacci::decompose(new Math_Integer($bigint));
  155.  * foreach ($series as $fib) {
  156.  *     $index = Math_Fibonacci::getIndexOf($fib);
  157.  *     echo "F(".$index->toString().") = ".$fib->toString()."\n";
  158.  * }
  159.  * // Finding the Fibonacci numbers that add up to 3141579834521345220291
  160.  * // F(104) = 2427893228399975082453
  161.  * // F(101) = 573147844013817084101
  162.  * // F(98) = 135301852344706746049
  163.  * // F(91) = 4660046610375530309
  164.  * // F(86) = 420196140727489673
  165.  * // F(83) = 99194853094755497
  166.  * // F(81) = 37889062373143906
  167.  * // F(79) = 14472334024676221
  168.  * // F(76) = 3416454622906707
  169.  * // F(74) = 1304969544928657
  170.  * // F(71) = 308061521170129
  171.  * // F(68) = 72723460248141
  172.  * // F(63) = 6557470319842
  173.  * // F(60) = 1548008755920
  174.  * // F(57) = 365435296162
  175.  * // F(53) = 53316291173
  176.  * // F(51) = 20365011074
  177.  * // F(49) = 7778742049
  178.  * // F(44) = 701408733
  179.  * // F(37) = 24157817
  180.  * // F(31) = 1346269
  181.  * // F(26) = 121393
  182.  * // F(20) = 6765
  183.  * // F(16) = 987
  184.  * // F(13) = 233
  185.  * // F(8) = 21
  186.  * // F(6) = 8
  187.  * // F(3) = 2
  188.  * 
  189.  * </pre>
  190.  *
  191.  * @author  Jesus M. Castagnetto <jmcastagnetto@php.net>
  192.  * @version 0.8
  193.  * @access  public
  194.  * @package Math_Fibonacci
  195.  */
  196. class Math_Fibonacci {/*{{{*/
  197.  
  198.     /**
  199.      * Calculates a Fibonacci number using the (exact) golden ratio equation:
  200.      * F(n) = (PHI^n - phi^n)/sqrt(5) [Lucas formula]
  201.      * for terms from [0,46]
  202.      * from [47,500] it uses a lookup table
  203.      * from then on uses the recursive addition
  204.      *
  205.      * @param mixed $n the index of the Fibonacci number to calculate, as an integer or a Math_Integer number
  206.      * @return mixed numeric on success, PEAR_Error otherwise
  207.      * @access public
  208.      */
  209.     function &term($n) {/*{{{*/
  210.         if (Math_IntegerOp::isMath_Integer($n)) {
  211.             $idx =& $n;
  212.         } elseif (is_numeric($n) && $n >= 0) {
  213.             $idx =& new Math_Integer($n);
  214.         } else {
  215.             return PEAR::raiseError("The parameter $n is not a Math_Integer object");
  216.         }
  217.         
  218.         $table =& $GLOBALS['_fibonacciTable'];
  219.  
  220.         // shortcut and check if it is already a cached value
  221.         if (isset($table[$idx->toString()])) {
  222.             return new Math_Integer($table[$idx->toString()]);
  223.         }
  224.         
  225.         // from index [0,46] use the fast algorithm
  226.         $cmp_0 = Math_IntegerOp::compare($idx, new Math_Integer(0));
  227.         $cmp_46 = Math_IntegerOp::compare($idx, new Math_Integer(46));
  228.         if ( ($cmp_0 >= 0) && ($cmp_46 <= 0) ) {
  229.             $val = intval($idx->toString());
  230.             $fn = (pow(MATH_PHI, $val) - pow(MATH_phi, $val))/sqrt(5);
  231.             // add to lookup table
  232.             $table[$val] = $fn;
  233.             return new Math_Integer(strval($fn));
  234.         }
  235.         // from [47,500] use the lookup table
  236.         $cmp_500 = Math_IntegerOp::compare($idx, new Math_Integer(500));
  237.         if ( ($cmp_46 > 0) && ($cmp_500 <= 0) ) {
  238.             return new Math_Integer($table[$idx->toString()]);
  239.         } else {
  240.             // calculate and cache the values
  241.             $a = new Math_Integer($table['499']);
  242.             $b = new Math_Integer($table['500']);
  243.             $pos = new Math_Integer('501');
  244.             $one = new Math_Integer('1');
  245.             while (Math_IntegerOp::compare($pos,$idx) <= 0) {
  246.                 $c = Math_IntegerOp::add($a, $b);
  247.                 $table[$pos->toString()] = $c->toString();
  248.                 $a = $b;
  249.                 $b = $c;
  250.                 $pos = Math_IntegerOp::add($pos, $one);
  251.             }
  252.             return $c;
  253.         }
  254.         
  255.     }/*}}}*/
  256.  
  257.     /**
  258.      * Returns a series of Fibonacci numbers using the given limits.
  259.      * Method accepts two parameters, of which the second one is
  260.      * optional. If two parameters are passed, the first one will be 
  261.      * lower bound and the second one the upper bound. If only one
  262.      * parameter is passed, it will be the upper bound, and the lower
  263.      * bound will be 0 (zero).
  264.      *
  265.      * @param integer $idx1 the lower index for the series (if two parameters) were passed, or the upper index if only one was given.
  266.      * @param optional integer $idx2 the upper index for the series
  267.      * @return mixed on success, an array of integers where the keys correspond to the indexes of the corresponding Fibonacci numbers, or PEAR_Error othewise
  268.      * @access public
  269.      */
  270.     function series($idx1, $idx2=null) {/*{{{*/
  271.         if (is_integer($idx1) && $idx1 > 0) {
  272.             if ($idx2 == null) {
  273.                 $lower_bound = 0;
  274.                 $upper_bound = $idx1;
  275.             } elseif (is_integer($idx2)) {
  276.                 if ($idx2 < 0) {
  277.                     return PEAR::raiseError("Upper limit $idx2 cannot be negative");
  278.                 } elseif ($idx2 < $idx1) {
  279.                     return PEAR::raiseError("Upper limit cannot be smaller than lower limit");
  280.                 } else {
  281.                     $lower_bound = $idx1;
  282.                     $upper_bound = $idx2;
  283.                 }
  284.             }
  285.             $fibSeries = array();
  286.             for ($i=$lower_bound; $i <= $upper_bound; $i++) {
  287.                 $fibSeries[$i] =& Math_Fibonacci::term($i);
  288.             }
  289.             return $fibSeries;
  290.         } else {
  291.             return PEAR::raiseError("The parameter $idx1 is not a valid integer");
  292.         }
  293.     }/*}}}*/
  294.  
  295.     /**
  296.      * Determines if a particular integer is part of the Fibonacci series
  297.      *
  298.      * @param integer $num
  299.      * @return mixed TRUE if it is a Fibonacci number, FALSE if not, PEAR_Error if the parameter was not an integer
  300.      * @access public
  301.      * @see Math_Fibonacci::term
  302.      */ 
  303.     function isFibonacci($num) {/*{{{*/
  304.         if (!Math_IntegerOp::isMath_Integer($num)) {
  305.             return PEAR::raiseError('Not a valid Math_Integer object'); 
  306.         }
  307.         $n = Math_Fibonacci::_estimateN($num);
  308.         $intcalc =& Math_Fibonacci::term($n); 
  309.         $cmp = Math_IntegerOp::compare($num, $intcalc);
  310.         return ($cmp == 0);
  311.     }/*}}}*/
  312.  
  313.     /**
  314.      * Decomposes an integer into a sum of Fibonacci numbers
  315.      * 
  316.      * @param integer $num
  317.      * @return mixed an array of Fibonacci numbers on success, PEAR_Error otherwise 
  318.      * @access public
  319.      */
  320.     function decompose($num) {/*{{{*/
  321.         if (!Math_IntegerOp::isMath_Integer($num)) {
  322.             return PEAR::raiseError('Not a valid Math_Integer object'); 
  323.         }
  324.         $err = Math_Fibonacci::_recDecompose($num, &$sum);  
  325.         if (PEAR::isError($err)) {
  326.             return $err;
  327.         }
  328.         $check = new Math_Integer(0);
  329.         foreach($sum as $fib) {
  330.             if (PEAR::isError($fib)) {
  331.                 return $fib;
  332.             } else {
  333.                 $check = Math_IntegerOp::add($check, $fib);
  334.             }
  335.         }
  336.         $int =& new Math_Integer($num);
  337.         if (Math_IntegerOp::compare($num,$check) == 0) {
  338.             return $sum;
  339.         } else {
  340.             $numstr = $num->toString();
  341.             $sumsrt = $check->toString;
  342.             return PEAR::raiseError("Number and sum do not match: $numstr != $sumstr");
  343.         }
  344.     }/*}}}*/
  345.  
  346.     /**
  347.      * Finds the Fibonacci number closest to an given integer
  348.      *
  349.      * @param integer $num
  350.      * @return mixed a Fibonacci number (integer) on success, PEAR_Error otherwise
  351.      * @access public
  352.      */
  353.     function closestTo($num) {/*{{{*/
  354.         if (!Math_IntegerOp::isMath_Integer($num)) {
  355.             return PEAR::raiseError("Invalid parameter: not a Math_Integer object");
  356.         }
  357.         $n = Math_Fibonacci::_estimateN($num);
  358.         $fib1 =& Math_Fibonacci::term($n);
  359.         $cmp = Math_IntegerOp::compare($fib1,$num);
  360.         if ($cmp == 0) {
  361.             return $fib1;
  362.         } elseif ($cmp == 1) { // overshoot, see n - 1
  363.             $new_n = Math_IntegerOp::sub($n, new Math_Integer(1));
  364.         } else { // undeshoot, try n + 1
  365.             $new_n = Math_IntegerOp::add($n, new Math_Integer(1));
  366.         }
  367.         $fib2 = Math_Fibonacci::term($new_n);
  368.         $d1 = Math_IntegerOp::abs(Math_IntegerOp::sub($fib1, $num));
  369.         $d2 = Math_IntegerOp::abs(Math_IntegerOp::sub($fib2, $num));
  370.         $cmp = Math_IntegerOp::compare($d1, $d2);
  371.         if ($cmp == -1 || $cmp == 0) {
  372.             return $fib1;
  373.         } else {
  374.             return $fib2;
  375.         }
  376.     }/*}}}*/
  377.     
  378.     /**
  379.      * Gets the index in the Fibonacci series of a given number.
  380.      * If the integer given is not a Fibonacci number a PEAR_Error object
  381.      * will be returned.
  382.      * 
  383.      * @param integer $num the Fibonacci number
  384.      * @return mixed the index of the number in the series on success, PEAR_Error otherwise.
  385.      * @access public
  386.      */
  387.     function getIndexOf($num) {/*{{{*/
  388.         if (!Math_IntegerOp::isMath_Integer($num)) {
  389.             return PEAR::raiseError("Invalid parameter: not a Math_Integer object");
  390.         }
  391.         // check in the lookup table
  392.         
  393.         $n = Math_Fibonacci::_estimateN($num);
  394.         $fibn = Math_Fibonacci::term($n);
  395.         $cmp = Math_IntegerOp::compare($num, $fibn);
  396.         if ($cmp == 0) {
  397.             return $n;
  398.         } else {
  399.             return PEAR::raiseError("Integer $num is not a Fibonacci number");
  400.         }
  401.     }/*}}}*/
  402.  
  403.     /**
  404.      * Recursive utility method used by Math_Fibonacci::decompose()
  405.      * 
  406.      * @param integer $num
  407.      * @param array $sum array of Fibonacci numbers
  408.      * @return mixed null on success, PEAR_Error otherwise
  409.      * @access private
  410.      */
  411.     function _recDecompose($num, &$sum) {/*{{{*/
  412.         if (!Math_IntegerOp::isMath_Integer($num)) {
  413.             return PEAR::raiseError('Not a valid Math_Integer object'); 
  414.         }
  415.         if (!is_array($sum)) {
  416.             $sum = array();
  417.         }
  418.         $n = Math_Fibonacci::_estimateN($num);
  419.         if (PEAR::isError($n)) {
  420.             return $n;
  421.         }
  422.         $fibn = Math_Fibonacci::term($n);
  423.         if (PEAR::isError($fibn)) {
  424.             return $fibn;
  425.         }
  426.         $cmp = Math_IntegerOp::compare($fibn, $num);
  427.         if ($cmp == 0) {
  428.             $sum[] = $fibn;
  429.             return null;
  430.         } elseif ($cmp == -1) {
  431.             $sum[] = $fibn;
  432.             $newnum = Math_IntegerOp::sub($num, $fibn);
  433.             Math_Fibonacci::_recDecompose($newnum, &$sum);
  434.         } elseif ($cmp == 1) {
  435.             $n_1 = Math_IntegerOp::sub($n, new Math_Integer(1));
  436.             if (PEAR::isError($n_1)) {
  437.                 return $n_1;
  438.             }
  439.             $fibn_1 = Math_Fibonacci::term($n_1);
  440.             if (PEAR::isError($fibn_1)) {
  441.                 return $fibn_1;
  442.             }
  443.             $sum[] = $fibn_1;
  444.             $newnum = Math_IntegerOp::sub($num, $fibn_1);
  445.             Math_Fibonacci::_recDecompose($newnum, &$sum);
  446.         }
  447.     }/*}}}*/
  448.  
  449.     /**
  450.      * Estimates the approximate index for a given number
  451.      * It uses the approximate formula:
  452.      * F(n) ~ (PHI^n)/sqrt(5), where '~' means the 'closest integer to'
  453.      * This equation is based on the relation: phi = -1/PHI
  454.      * Which turns Lucas' formula into:
  455.      * F(n) = (PHI^2n + 1)/(PHI^n * sqrt(5))
  456.      * From which we get the formula above, after making the approximation:
  457.      * (PHI^2n + 1) -> (PHI^2n)
  458.      *
  459.      * @param integer $num
  460.      * @return integer the approximate index
  461.      * @access private
  462.      */
  463.     function &_estimateN(&$num) {/*{{{*/
  464.         if (Math_IntegerOp::isMath_Integer($num)) {
  465.             $f = $num->toString();
  466.         } else {
  467.             $f = $num;
  468.         }
  469.         return Math_Fibonacci::_closestInt((log($f) + MATH_LNSQRT5) / MATH_LNPHI);
  470.     }/*}}}*/
  471.     
  472.     /**
  473.      * Finds the closest integer to a given number
  474.      *
  475.      * @param numeric $num
  476.      * @return integer
  477.      * @access private
  478.      */
  479.     function &_closestInt($num) {/*{{{*/
  480.         $f = floor($num);
  481.         $c = ceil($num);
  482.         return new Math_Integer(($num - $f) < ($c - $num) ? $f : $c);
  483.     }/*}}}*/
  484.  
  485. }/* End of Math_Fibonacci }}}*/
  486.  
  487. // vim: ts=4:sw=4:et:
  488. // vim6: fdl=1:
  489. ?>
  490.